package 抽象数据类型;

/**
 * @description:
 * @author: ywk
 * @date: 2021-03-02
 */
public class 优先队列 {
    public static class MaxPQ<T extends Comparable<T>> {
        private T[] pq;
        private int N = 0;
        private boolean desc;//1:最大堆，2:最小堆

        public MaxPQ(int cap, boolean desc) {
            pq = (T[]) new Comparable[cap];
            this.desc = desc;
        }

        public T max() {
            return pq[1];
        }

        public void insert(T t) {
            N++;
            pq[N] = t;
            swim(N);
        }

        public T delMax() {
            T max = pq[1];
            exch(1, N);
            pq[N] = null;
            N--;
            sink(1);
            return max;
        }

        private void swim(int k) {
            while (k > 1 && less(parent(k), k)) {
                exch(parent(k), k);
                k = parent(k);
            }
        }

        private void sink(int k) {
            while (left(k) <= N) {
                int older = left(k);
                if (right(k) < N && less(older, right(k))) {
                    older = right(k);
                }
                if (less(older, k)) {
                    break;
                }
                exch(k, older);
                k = older;
            }
        }

        /* 交换数组的两个元素 */
        private void exch(int i, int j) {
            T temp = pq[i];
            pq[i] = pq[j];
            pq[j] = temp;
        }

        public int parent(int k) {
            return k / 2;
        }

        public int left(int k) {
            return k * 2;
        }

        public int right(int k) {
            return k * 2 + 1;
        }

        /* pq[i] 是否⽐ pq[j] ⼩？ */
        private boolean less(int i, int j) {
            return (desc == true ? 1 : -1) * pq[i].compareTo(pq[j]) < 0;
        }

        public T[] getPq() {
            return pq;
        }

        public void setPq(T[] pq) {
            this.pq = pq;
        }

        public int getN() {
            return N;
        }

        public void setN(int n) {
            N = n;
        }

        public boolean isDesc() {
            return desc;
        }

        public void setDesc(boolean desc) {
            this.desc = desc;
        }
    }


    public void heapSort(int[] arr) {
        MaxPQ<Integer> pq = new MaxPQ<>(arr.length + 1,true);
        for (int i = 0; i < arr.length; i++) {
            pq.insert(arr[i]);
        }
        int n = pq.N;
        for (int i = 0; i < n; i++) {
            arr[i] = pq.delMax();
        }
    }

    public static void main(String[] args) {
        优先队列 test = new 优先队列();
        int[] ints = {1, 1, 3, 4, 1, 6, 0, 3};
        test.heapSort(ints);
        for (int anInt : ints) {
            System.out.print(anInt + "\t");
        }

    }
}
